P2894 [USACO08FEB]酒店Hotel

这道题明显是线段树的板题,至于考试时因为懒标记的小问题只有20分,我也很无奈

进入正题,既然要修改查询区间内连续的一段元素,似曾相识的感觉
我们等价的把空房子看为1,住人的房子看为0。

我们维护三个值: numnum表示这个区间最长的一段连续1'1'串 , lnumlnum表示这个区间从左端点开始的最长连续1'1'串 , rnumrnum表示这个区间从右端点开始的最长连续1'1'串。

然后,用f记录区间状态(懒标记),f=1f=1表示全为1,f=0f=0表示全为0,f=2f=2什么都没发生。

然后,就照着线段树的模板写。稍微麻烦一点的是区间修改后的维护与查询操作,下面来讲解一下。

1.区间修改后的维护(pushuppushup函数)

在得到两个子区间后,我们需要根据他们得出大区间的信息。(废话)

1.lnumlnumrnumrnum

显然,大区间的lnumlnum就等于左区间的lnumlnum,特殊情况下,当左区间全为1时,大区间的lnumlnum等于左区间的长度加上右区间的lnumlnumrnumrnum同理。

2.numnum

显然,大区间的numnum可能是两个小区间的numnum的较大值,同时,也可能是由左区间的rnumrnum和右区间lnumlnum的拼接而成的连续‘1’串。

2.区间查询(FindFind函数)

应该比较好理解,哪个区间足够就查询哪个区间吗,注意输出最小的值,从左到右依次查询。

#include <cstdio>
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f

const int MAXN = 50000;
int n,m;
struct node{
	int l , r , f;
	int num , lnum , rnum;
}Tree[ 4 * MAXN + 5 ];

int Max( int x , int y ) {
	return x > y ? x : y;
}
int Min( int x , int y ) {
	return x < y ? x : y;
}

void Build( int x , int l , int r ) {
	Tree[ x ].l = l , Tree[ x ].r = r , Tree[ x ].f = 2;
	Tree[ x ].lnum = Tree[ x ].rnum = Tree[ x ].num = Tree[ x ].r - Tree[ x ].l + 1;
	if( l == r ) return;
	
	int Mid = ( l + r ) / 2;
	Build( ls , l , Mid );
	Build( rs , Mid + 1 , r );
}
void pushup( int x ) {
	Tree[ x ].lnum = Tree[ ls ].lnum;
	if( Tree[ ls ].num == Tree[ ls ].r - Tree[ ls ].l + 1 ) Tree[ x ].lnum = Tree[ ls ].num + Tree[ rs ].lnum;
	
	Tree[ x ].rnum = Tree[ rs ].rnum;
	if( Tree[ rs ].num == Tree[ rs ].r - Tree[ rs ].l + 1 ) Tree[ x ].rnum = Tree[ rs ].num + Tree[ ls ].rnum;
	
	Tree[ x ].num = Max( Max( Tree[ ls ].num , Tree[ rs ].num ) , Tree[ ls ].rnum + Tree[ rs ].lnum );
}
void pushdown( int x ) {
	if( Tree[ x ].l == Tree[ x ].r )
		return;
	if( Tree[ x ].f == 0 ) {
		Tree[ ls ].num = 0 , Tree[ ls ].f = 0;
		Tree[ rs ].num = 0 , Tree[ rs ].f = 0;
		Tree[ ls ].lnum = Tree[ ls ].rnum = 0;
		Tree[ rs ].lnum = Tree[ rs ].rnum = 0;
		Tree[ x ].f = 2;
	}
	if( Tree[ x ].f == 1 ) {
		Tree[ ls ].num = Tree[ ls ].r - Tree[ ls ].l + 1 , Tree[ ls ].f = 1;
		Tree[ rs ].num = Tree[ rs ].r - Tree[ rs ].l + 1 , Tree[ rs ].f = 1;
		Tree[ ls ].lnum = Tree[ ls ].rnum = Tree[ ls ].num;
		Tree[ rs ].lnum = Tree[ rs ].rnum = Tree[ rs ].num;
		Tree[ x ].f = 2;
	}
}
void Insert( int x , int l , int r , int k ) {
	if( l > Tree[ x ].r || Tree[ x ].l > r )
		return;
	if( l <= Tree[ x ].l && Tree[ x ].r <= r ) {
		Tree[ x ].f = k;
		Tree[ x ].num = k == 1 ? Tree[ x ].r - Tree[ x ].l + 1 : 0;
		Tree[ x ].lnum = Tree[ x ].rnum = Tree[ x ].num;
		return;
	}
	pushdown( x );
	Insert( ls , l , r , k );
	Insert( rs , l , r , k );
	pushup( x );
}
int Find( int x , int k ) {
	if( Tree[ x ].l == Tree[ x ].r ) return Tree[ x ].l;
	pushdown( x );
	if( Tree[ ls ].num >= k ) return Find( ls , k );
	if( Tree[ ls ].rnum + Tree[ rs ].lnum >= k ) return Tree[ ls ].r - Tree[ ls ].rnum + 1;
	if( Tree[ rs ].num >= k ) return Find( rs , k );
}
int main( ) {
	//freopen("hotel.in","r",stdin);
	//freopen("hotel.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	Build( 1 , 1 , n );
	int op,x,d;
	for( int i = 1 ; i <= m ; i ++ ) {
		scanf("%d",&op);
		if( op == 1 ) {
			scanf("%d",&d);
			if( Tree[ 1 ].num < d ) {
				printf("0\n");
				continue;
			}
			int r = Find( 1 , d );
			Insert( 1 , r , r + d - 1 , 0 );
			printf("%d\n",r);
		}
		else if( op == 2 ) {
			scanf("%d %d",&x,&d);
			Insert( 1 , x , x + d - 1 , 1 );
		}
	}
	return 0;
}